package com.itzmn.newcode.offer1;


import com.itzmn.newcode.offer.HasSubTree;

import java.io.Serializable;

/**
 * @Author: 张梦楠
 * @Date: 2018/12/19 14:35
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 树的子结构
 *
 *  输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
 *
 *  判断这颗树和左边是否有重合，每个节点都是一样的
 *
 */
public class _17_SubstructureOfTheTree extends Tree{

    public static void main(String[] args) {

        new _17_SubstructureOfTheTree().test();
    }

    private void test() {


        int[] arrs = {8,8,-1,9,-1,2,-1,5};
        TreeNode binaryTreeWithOnlyOneNull = createBinaryTreeWithOnlyOneNull(arrs);
        InOrderTraversal(binaryTreeWithOnlyOneNull);
        int[] arrs1 = {8,9,3};
        TreeNode treeWithOnlyOneNull = createBinaryTreeWithOnlyOneNull(arrs1);
        InOrderTraversal(treeWithOnlyOneNull);
        boolean b = HasSubtree(binaryTreeWithOnlyOneNull, treeWithOnlyOneNull);

        System.out.println(b);

    }


    public boolean HasSubtree(TreeNode root1,TreeNode root2) {

        boolean result = false;
        if (root1 != null && root2 != null){
            // 两个跟节点一样，比较下面的子节点
            if (root1.val == root2.val){

                result = check(root1, root2);
                // 如果比较的不是，那么将这个节点与左子树的节点相比
                if (!result){

                    result = HasSubtree(root1.left, root2);
                }
                // 如果比较的不是，那么将这个节点与右子树的节点相比
                if (!result){
                    result = HasSubtree(root1.right, root2);
                }
            }
        }

        return result;
    }

    public boolean check(TreeNode root1,TreeNode root2){
        // 如果左边树为null，右边还没遍历完，那肯定不是
        if (root1 == null && root2 != null){
            return false;
        }
        // 如果右边遍历完了，那就是
        if (root2 == null){
            return true;
        }
        // 如果两个节点的值不一样，那就不是
        if (root1.val != root2.val){
            return false;
        }

        // 当两边的树的两个节点都一样就是
        return check(root1.left,root2.left) && check(root1.right,root2.right);
    }


}
